package com.hdu.hot100.list;

import java.util.List;

public class lc19 {


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {

            /**
             *    n == 2
             *                       slow                        fast
             *    1  ->   2   ->    3   ->   4   ->   5   ->   null
             *    fast 指向 null 的时候  slow 指向 要删除的节点的前一个节点
             *
             *
             *    slow
             *    fast
             *    dummy   ->    1  ->   2   ->    3   ->   4   ->   5   ->   null
             *
             *
             *    slow
             *                                    fast
             *    dummy   ->    1  ->   2   ->    3   ->   4   ->   5   ->   null
             */
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode slow = dummy;
            ListNode fast = dummy;
            for (int i = 0; i <= n; i++)
            {
                fast = fast.next;
            }
            while (fast != null)
            {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
        }
    }
}
